package org.shj.algorithm.string;

/**
 * 最长回文子串问题
 *   注意：回文串有单双字符的区别。如： aba 和 abba 都是回文串
 *
 * 解题思路一：
 * 1. 把原字符串处理成不需要考虑单双的字符串。
 *    方法：在字符之间及首尾都插入一个特殊字符。
 *    如：aba -->  a#b#a    abba --> a#b#b#a
 *    这样处理后，不管原字符串长度是单还是双，都会变成单数个的字符串
 * 2. 取得以每一位为中心时的最长回文串的数组，记为 P
 *   S =  # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
 *   P =  1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
 *   P[i] - 1 即为最长回文子串的长度。 示例中是： 6 - 1 = "12321" 的长度
 *   注意：只考察 P[i] 为偶数的情况，因为奇数时，其对应的是插入的特殊字符。
 *
 * 如何求 P ?
 *  1. 用暴力的方法，可以简单的求出P，但显然这不是最佳的算法。
 *  2. 当计算 P[i] 时，利用前面得到的 P[0]~P[i-1] 结果，在某些情况下，可以直接或部分获得 P[i] 的值。
 *     什么情况下能直接或部分获得 P[i] 的值呢？ 0 ~ i-1 的某个位置（记为 k）, 以 k 为中心的回文串的
 *     最右面的字符位置是 k + P[k] - 1 ，记为 Rk，最左面的字符位置是 k - P[k] + 1, 记为 Lk。
 *     当 i < Rk 时， 即 i 处于以 k 为中心的回文串的右半部分时，可以直接或部分获得 P[i] 的值。
 *     如果处于以 k 为中心的回文串的外面时，只能暴力求 P[i] 的值。为了尽量使 i < Rk，需要求得 Rk 的最大值。
 *     2.1 如下面情况，当求第2个 3 这个位置(i=13)的 P[i] 时，可以直接获得 P[i]=P[5]。 因为 k=9 时（此位置的
 *         字符是5），P[9]=10。而 i=13 < 9+10-1，由回文串的对称性可知，i=13 与位置5(字符3) 必定是以位置9
 *         为中心对称的。
 *                 # 2 # 4 # 3 # 4 # 5 # 4 # 3 # 4 # 2 #
 *     2.2 未例字符串如下(未加特殊字符)，当求 i=4 的 P[i] 时，k=3 时，虽然 i 落在了 k 和 Rk 之间，但是 i
 *         关于 k 的对称点的位置是 j=2，其回文串的长度超出了 Lk 的位置，所以 P[i] 的值不能直接取 P[j] 的值。
 *         只能得到部分值，即 j 到 Lk 的长度。需要再计算超出部分是否也有回文
 *         i: 0 1 2 3 4 5
 *            3 5 3 5 3 5
 *       P[i] 1 2 3 3
 *
 * 解题思路二：
 *    动态规划：
 *    1. 用一个数组 dp[i][j] 记录 i 位置的字符到 j 位置的字符的回文串的长度。只需记录 j > i 的部分
 *    2. 当 j - i = 1 时，如果 s[j]=s[i]，则 dp[i][j] = 2; 否则为 0
 *    3. 当 j - i >=2 时，
 *       3.1 若s[i]==s[j]：
 *            若dp[i+1][j-1]>0，则dp[i][j]= dp[i + 1][j - 1] + 2; 否则dp[i][j]= 0;
 *
 *       3.2 若s[i] != s[j]，则 dp[i][j]=0
 *
 * @author Shen Huang Jian
 * @date 2019/4/1
 */
public class Manacher {
    public static void main(String[] args){
        //String str = "12212321";
        String str="dsfsdhadhfkdsdsfsdhadhdsfsdhadhfkddsfsdhadhfkdsahfksadhdsfsdhadhfkdsahfksadhfksddsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsksahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsk";
        //String str = "aabaacaab";
        baoli(str);
        manacher(str);
        dongGui(str);
    }

    //用于验证其它算法的正确性
    private static void baoli(String str){
        System.out.println("暴力算法");
        String sb = fillSpecialChar(str);
        int len = sb.length();
        int p[] = new int[len];
        //初始化为1
        for(int i = 0 ; i < len; i++){
            p[i] = 1;
        }

        int cnt = 0;

        for(int i = 0; i < len; i++){
            int n = 1;
            while(i - n >=0 && i+n < len && sb.charAt(i-n) == sb.charAt(i+n)){
                cnt++;
                p[i] = p[i] + 1;
                n++;
            }
        }
        int max = 0;
        int maxIndex = 1;
        for(int i = 1; i < len; i += 2){
            if(p[i] > max){
                max = p[i];
                maxIndex = i;
            }
        }
        System.out.println("循环次数：" + cnt);
        print(max, maxIndex, sb);
    }

    private static String fillSpecialChar(String str){
        // 填充特殊字符
        String special = "#";
        StringBuilder sb = new StringBuilder(special);
        for(char ch : str.toCharArray()){
            sb.append(ch).append(special);
        }
        return sb.toString();
    }

    private static void manacher(String str){
        System.out.println("马拉车算法");
        String sb = fillSpecialChar(str);

        int len = sb.length();
        int[] p = new int[len];

        p[0] = 1;
        int k = 0;

        int max = p[0];
        int maxIndex = 0;
        int cnt=0;
        for(int i = 1; i < len; i++){
            int rk = k + p[k] - 1;
            int lk = k - p[k] + 1;

            if(i < rk){
                int j = 2 * k - i;
                p[i] = (rk - i) > p[j] ? p[j] : (rk-i);

                if(j - p[j] < lk){//部分获得 p[j] 的值的情况，需要再另外判断超出 rk 的部分
                    int n = 1;
                    while (rk + n < len && 2*i - rk - n >= 0 &&
                            sb.charAt(rk + n) == sb.charAt(2*i - rk - n)){
                        p[i] = p[i] + 1;
                        n++;
                        cnt++;
                    }
                }else {
                    cnt++;
                }
            }else{// 只能暴力求解
                p[i] = 1;
                int n = 1;
                while(i + n < len && i - n >=0 && sb.charAt(i + n) == sb.charAt(i - n)){
                    p[i] = p[i] + 1;
                    n++;
                    cnt++;
                }
            }

            if(p[i] >= max && p[i] % 2 == 0){ // 只考虑偶数的情况
                max = p[i];
                maxIndex = i;
            }

            if(i + p[i] > k + p[k]){//更新 k 值
                k = i;
            }
        }

        System.out.println("循环次数：" + cnt);
        print(max, maxIndex, sb);
    }

    private static void print(int max, int maxIndex, String str){
        int maxLen = max - 1;
        System.out.println("最长回文子串的长度是：" + maxLen);
        System.out.print("最长回文子串是：");
        //首尾两个肯定是加入的特殊字符
        for(int i = maxIndex - maxLen + 1; i <= maxIndex + maxLen - 1; i += 2){
            System.out.print(str.charAt(i));
        }
        System.out.println();
    }

    /**
     *
     * @param str
     * @return
     */
    private static void dongGui(String str){
        System.out.println("动态规划法：");
        int len = str.length();
        int[][] dp = new int[len][len];
        for(int i = 0 ; i < len; i++){
            dp[i][i] = 1;
        }

        int start = 0;
        int max = 1;
        for(int j = 0; j < len; j++){
            for(int i = j - 1; i >= 0; i--){
                if(str.charAt(i) == str.charAt(j)){
                    if(j - i == 1){
                        dp[i][j] = 2;
                    }else {
                        if (dp[i + 1][j - 1] > 0) {
                            dp[i][j] = dp[i + 1][j - 1] + 2;

                        } else {
                            dp[i][j] = 0;
                        }
                    }
                }else{
                    dp[i][j] = 0;
                }

                if(dp[i][j] > max){
                    max = dp[i][j];
                    start = i;
                }
            }
        }

        System.out.println("最长回文子串的长度是：" + max);
        System.out.print("最长回文子串是：" + str.substring(start, start + max));
    }

}
